package leetcode_ago.top_k;
/**
 * 题目：查找和最小的k个数对（pair:数对）
 * 给定两个以升序排列的整数数组nums1和nums2 ,以及一个整数 k 。定义一对值 (u,v)，其中第一个元素来自 nums1，第二个元素来自 nums2 。
 * 请找到和最小的k个数对(u1,v1),(u2,v2)...(uk,vk)
 * 1 <= nums1.length, nums2.length <= 105
 * -109 <= nums1[i], nums2[i] <= 109
 * nums1 和 nums2 均为升序排列
 * 1 <= k <= 1000
 */
import java.util.*;

/**
 * 分析：
 * 1.求和最小的k个数对，topK问题，用大堆（JDK内部默认是最小堆）
 * 2.k有可能大于数组长度：[1,2],[1],求和最小的三个数对，此时组合起来只有两个数对
 * 3.学会使用类，类中两个变量u、v,u表示第一个数组的元素，v表示第二个数组的元素
 * 细节难点：
 * 1.JDK内部默认最小堆，要转化为最大堆：用到比较器改造最小堆变为最大堆实现
 * 2.k值大于数组长度遍历到数组长度即可遍历结束，k值小于数组长度数组遍历k个元素即可
 * 即遍历两个数组时循环条件终止条件：for(int i=0;i<Math.min(nums1.length,k);i++)
 * （升序数组，题目找最小元素组合数对，k个后面的一定不是要用到的元素）
 * 3.当最后取出队列元素时，除了前k个这个条件，另外，由于可能k>数组长导致不到k队列已经空了，此时也算结束无需再操作
 * 即取出元素时循环的终止条件：for (int i = 0; i < k&&(!queue.isEmpty()); i++)
 * 思路：
 * 1.定义数对的类。构建最大堆
 * 2.扫描遍历这两个数组(u来自第一个数组，v来自第二个数组),k个键值对放入最大堆
 *   放够后开始比较是否小于堆顶元素，小于无需入队，大于堆顶出队当前数对入队
 * 3.前k个pair对象依次出队
 */
public class Num373_KSmallestPairs {
    private class Pair{
        int u;
        int v;
        public Pair(int u, int v) {
            this.u = u;
            this.v = v;
        }
    }
    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        //1.构建出最大堆的优先级队列，实现比较器（定义出比较方法）
        //最大堆存的元素是<Pair>，此时元素的大小关系为pair对象中u+v的值越大，认为元素越大【最大堆大的先出就达到最后剩和最小的数对】
        Queue<Pair> queue=new PriorityQueue<>(new Comparator<Pair>() {
            @Override
            public int compare(Pair o1, Pair o2) {
                return (o2.u+o2.v)-(o1.u+ o1.v);
            }
        });
        //2.遍历两个数组，注意数组循环遍历的中止条件:k>数组长度时取到数组长度即可，小于时取到k即可
        //重点:k值可能比数组长度大，此时只需要遍历到数组长度就好
        //k<数组长度时，数组取值只用取到k，因为元素按值升序，k后的一定是大值，用不到
        //综合，所以循环的终止条件就是：Math.min(nums.length,k),取键值对个数k与数组长度的较小值【难点】
        for (int i = 0; i < Math.min(nums1.length,k); i++) {
            for (int j = 0; j < Math.min(nums2.length, k); j++) {
                if(queue.size()<k){
                    queue.offer(new Pair(nums1[i],nums2[j]));
                }else{
                    int add=nums1[i]+nums2[j];
                    Pair pair=queue.peek();
                    if(add>(pair.u+ pair.v)){
                        continue;
                    }else{
                        queue.poll();
                        queue.offer(new Pair(nums1[i],nums2[j]));
                    }
                }
            }
        }
        //此时优先级队列中就存储了最大的k个数对，出队即可.
        //注意出队循环中止条件：出k个数对，当数组长<k时，可能还未遍历到k就提前出完了，所以要加上队列不为空的条件
        //返回值是二维数组,要的返回值是这些数对
        List<List<Integer>> ret=new ArrayList<>();
        for (int i = 0; i < k && (!queue.isEmpty()); i++) {
            List<Integer> temp=new ArrayList<>();
            Pair pair=queue.poll();
            temp.add(pair.u);
            temp.add(pair.v);
//            temp.add(queue.poll().u);
//            temp.add(queue.poll().v);
            ret.add(temp);
        }
        return ret;
    }
}
